package fun.coding.jeffreys.judge;

public class LongestCommonSubstring {

	public static void main(String[] args) {
		LongestCommonSubstring ins = new LongestCommonSubstring();
		System.out.println(ins.longestCommonSubstring("baozi", "aoi"));
	}
	
	// For each prefix pair, look for the largest suffix
	// This essentially enumerates all the substring, with prefix and suffix
	// http://en.wikipedia.org/wiki/Longest_common_substring_problem
	public int longestCommonSubstring(String w1, String w2) {
		if (w1 == null || w2 == null) return -1;
		
		int l1 = w1.length();
		int l2 = w2.length();
		
		if (l1 == 0 || l2 == 0) {
			return 0;
		}
		
		int[][] lookup = new int[l1+1][l2+1];
		
		for (int i = 0; i <= l1; i++) {
			lookup[i][0] = 0;
		}
		for (int i = 0; i <= l2; i++) {
			lookup[0][i] = 0;
		}
		
		int max = Integer.MIN_VALUE;
		for (int i = 1; i <= l1; i++) {
			for (int j = 1; j <= l2; j++) {
				if (w1.charAt(i-1) == w2.charAt(j-1)) {
					lookup[i][j] = lookup[i-1][j-1] + 1;
				} else {
					lookup[i][j] = 0;
				}
				
				max = Math.max(lookup[i][j], max);
			}
		}
		
		return max;
	}

}
